This invention relates to circuit synthesis with sequential rules.
An approach to circuit synthesis makes use of an asynchronous system specification to produces a detailed hardware description for a synchronous system, in particular, a clocked digital circuit that functions according to the asynchronous system specification. That is, any sequence of states traversed at clock times of the clocked digital circuit is guaranteed to be a sequence (or subsequence) of states that may be traversed by the asynchronous system. A compiler can be used to accept the asynchronous system specification and automatically produce a corresponding synchronous circuit specification, for example, specified using the Verilog hardware description language (HDL). One such compiler that performs this task makes use of a Term Rewriting System (TRS) to specify the asynchronous system.
The TRS specification accepted by the compiler includes a set of rules, which are also referred to as guarded atomic actions. Each rule consists of a body and a guard. The body describes the execution behavior of the rule if it is enabled. That is, the body characterizes the change in the state of the system on application of the rule, where the state is define by the values of storage elements of the system, such as registers or FIFOs. The guard (or predicate) of a rule specifies the condition that needs to be satisfied for the rule to be executable. A rule Ri is written asrule Ri: when πi(s)s:=δi(s)where πi(s) represents the guard and s:=δi(s) represents the body of rule Ri.
One synthesis (i.e., compilation) approach generates combinational logic for each rule's predicate (π) and each rule's state update function (δ). For each clock cycle of the synchronous system, a scheduler chooses one of the rules whose predicate is true (i.e., a rule that is “executable” or “enabled”) and updates the state with the result of the corresponding update function (δ). This process repeats in every clock cycle.
Given any two rules Ra and Rb, a designer can specify a composite rule for the asynchronous specification that specifies that Rb executes after Ra as follows:rule Rab: when (πa(s)&πb(δa(s)))s:=δb(δa(s))
Because the original two rules are already in the system, such a composite rule can be added to the asynchronous system specification without introducing new illegal behavior. Addition of certain composite rules can enable more rules to be scheduled by the compiler to execute in a single cycle. However, each additional composite rule generally increases the amount of synthesized circuitry, such that addition of all or many possible composite rules can be combinatorially prohibitive. Also, introduction of certain composite rules can reduce achievable clocking rates by introducing long chains of combinational logic in the circuit synthesized by the compiler.
Source-to-source TRS transformation systems have been proposed in which new composed rules are added to a system. In one such approach, the new rules are produced by taking a cross product of all the rules in a system and filtered out those composite rules that are “uninteresting” in the following sense. For example, composition of R1 followed by R2 may be considered uninteresting if either R2 could not be enabled after R1 executed or if R1 and R2 could already be scheduled in a single cycle.